#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/14 20:55
# @USER    : Shengji He
# @File    : Triangle.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        """
        Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers
        on the row below.

        For example, given the following triangle

        [
             [2],

            [3,4],

           [6,5,7],

          [4,1,8,3]

        ]

        The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

        Note:
            - Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows
        in the triangle.

        :param triangle:
        :return:
        """
        n = len(triangle)
        f = [0] * n
        f[0] = triangle[0][0]

        for i in range(1, n):
            f[i] = f[i - 1] + triangle[i][i]
            for j in range(i - 1, 0, -1):
                f[j] = min(f[j - 1], f[j]) + triangle[i][j]
            f[0] += triangle[i][0]

        return min(f)


if __name__ == '__main__':
    print('done')
